#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <unordered_map>

using std::endl;
using std::cout;
using std::map;
using std::vector;
using std::priority_queue;
using std::unordered_map;

typedef struct v4times_s {
    int key;
    int value;
    int times;
} v4times_t;

class Compare {
public:
    bool operator()(const v4times_t& rhs, const v4times_t& lhs) {
        return rhs.times > lhs.times;
    }
};

class LRUCache {
public:
    LRUCache(int capacity);
    void get(int key);
    void put(int key, int value);
    void check_pri();
private:
    int _capacity;
    unordered_map<int, v4times_t> _cache;
    priority_queue<v4times_t, vector<v4times_t>, Compare> _pri_que;
};

LRUCache::LRUCache(int capacity) : _capacity(capacity) {}

void LRUCache::get(int key) {
    auto it = _cache.find(key);
    if (it != _cache.end()) {
        cout << "++ times" << endl;
        it->second.times++;
        cout << it->second.times << endl;

        priority_queue<v4times_t, vector<v4times_t>, Compare> temp_queue;
        while (!_pri_que.empty()) {
            v4times_t temp = _pri_que.top();
            _pri_que.pop();
            if (temp.key == key) {
                temp.times++;
            }
            temp_queue.push(temp);
        }
        _pri_que = temp_queue;
    } else {
        cout << "null" << endl;
    }
}

void LRUCache::put(int key, int value) {
    auto it2 = _cache.find(key);
    if (it2 != _cache.end()) {
        cout << "find value" << endl;
        it2->second.value = value;
    } else {
        cout << "find no but insert" << endl;
        v4times_t temp;
        if (_cache.size() == _capacity) {
            v4times_t leastUsed = _pri_que.top();
            _pri_que.pop();
            _cache.erase(leastUsed.key);
        }
        temp.key = key;
        temp.times = 1;
        temp.value = value;
        _cache.insert({ key, temp });
        _pri_que.push(temp);
    }
}

void LRUCache::check_pri() {
    if(!_pri_que.empty()) {
        v4times_t temp = _pri_que.top();
        cout << "key: " << temp.key << " value: " << temp.value << " times: " << temp.times << endl;
        //_pri_que.pop();
    }
}

int main() {
    LRUCache lruCache(3);
    lruCache.put(1, 2);
    lruCache.put(2, 4); //1
    lruCache.get(1);
    lruCache.get(1); //3
    lruCache.get(2); //2
    lruCache.put(3,5);
    lruCache.get(3); //2
    lruCache.get(3);//3
    lruCache.put(4,6); //1
    lruCache.get(2); //null
    lruCache.check_pri();
    return 0;
}